package com.chy.算法;

public class 二叉查找树 {

    //父节点
    Node parent;

    //删除
    public void delete(int value){
        //记录要删除的节点
        Node p = parent;
        //记录要删除的节点的父节点
        Node p_parent = null;
        //先找到要删除的元素及其父元素
        while (p != null){
            if (value < p.value){
                p_parent = p;
                p = p.left;
            }else if (value > p.value){
                p_parent = p;
                p = p.right;
            }else {
                //value == p.value
                break;
            }
        }
        if (p == null){
            return;
        }
        if (p.left != null && p.right != null){
            //p就是要删除的节点且要删除的节点有两个子节点
            Node rTree = p.right;
            Node rTree_parent = p; //rTree的父节点
            while (rTree.left != null){
                rTree_parent = rTree;
                rTree = rTree.left;
            }
            //用右子树中最小节点替换掉要删除的节点位置
            p.value = rTree.value;

            //把右子树中最小节点赋值给p，准备删除
            p = rTree;
            p_parent = rTree_parent;
        }
        //当要删除的节点只有一个叶子结点或者就是叶子结点
        Node child = null;
        if (p.right != null){
            child = p.right;
        }else if (p.left != null){
            child = p.left;
        }else {
            //叶子结点
            child = null;
        }
        //执行删除操作
        if (p_parent == null){
            //根节点
            parent = child;
        }else if (p_parent.left == p){
            p_parent.left = child;
        }else {
            p_parent.right = child;
        }
    }

    //查找
    public Node find(int value){
        Node node = parent;
        while (parent != null){
            if (node.value == value){
                return node;
            }else if (value < node.value){
                node = node.left;
            }else if (value > node.value){
                node = node.right;
            }
        }
        return null;
    }
    public Node find(Node head,int value){
        if (head.value == value){
            return head;
        }
        if (value < head.value){
            return find(head.left,value);
        }else {
            return find(head.right,value);
        }

    }

    //增加
    public boolean put(int value){
        if (parent == null){
            parent = creatNode(value);
            return true;
        }
        Node node = parent;
        while (node != null){
            if (node.value == value){
                //二叉查找树不能有相同的值
                return false;
            }
            if (value < node.value){
                //往左边插入
                if (node.left == null){
                    //左孩子为空直接插到左孩子上
                    node.left = creatNode(value);
                    return true;
                }
                node = node.left;
            }else {
                //往右边插入
                if (node.right == null){
                    //右孩子为空直接插到右孩子上
                    node.right = creatNode(value);
                    return true;
                }
                node = node.right;
            }
        }
        return false;
    }

    //构造叶子结点
    private Node creatNode(int value){
        return new Node(null,value,null);
    }
    //构造有子树的节点
    private Node creatNode(Node left, int value, Node right){
        return new Node(left,value,right);
    }
    //二叉查找树数据结构
    public static class Node{
        private int value;
        private Node left;
        private Node right;

        public Node(Node left, int value, Node right) {
            this.left = left;
            this.value = value;
            this.right = right;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static void main(String[] args) {
        二叉查找树 tree = new 二叉查找树();
        tree.put(7);
        tree.put(4);
        tree.put(13);
        tree.put(2);
        tree.put(5);
        tree.put(8);
        System.out.println(tree.find(8));
        Node n2 = new Node(null,2,null);
        Node n3 = new Node(null,3,null);
        Node n1 = new Node(n2,1,n3);
        System.out.println(tree.find(n1,1));

    }
}
